package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * 47. 全排列 II
 * 给定一个可包含重复数字的序列，返回所有不重复的全排列。
 * 示例:
 * 输入: [1,1,2]
 * 输出:
 * [
 * [1,1,2],
 * [1,2,1],
 * [2,1,1]
 * ]
 */

public class problems_047 {

    public static void main(String[] arge) {
        System.out.println(new Solution().permuteUnique(new int[]{1, 1, 2}));
    }

    static class Solution {
        List<List<Integer>> ret = new ArrayList<>();
        public List<List<Integer>> permuteUnique(int[] nums) {
            Stack<Integer> stack = new Stack<>();
            dfs(stack, nums);
            return ret;
        }
        private void dfs(Stack<Integer> stack, int[] nums){
            if(stack.size() == nums.length){
                List<Integer> list = new ArrayList<>();
                for (Integer index : stack.stream().collect(Collectors.toList())){
                    list.add(nums[index]);
                }
                if(!ret.contains(list)){
                    ret.add(list);
                }
                return ;
            }
            for (int i = 0; i < nums.length; i++) {
                if(stack.contains(i)) continue;
                stack.push(i);
                dfs(stack, nums);
                stack.pop();
            }
        }
    }
}
